A typical computer system includes a microprocessor, memory, and peripheral computer resources, e.g., monitor, keyboard, software programs, etc. The microprocessor has, among other components, arithmetic, logic, and control circuitry that interpret and execute instructions from a computer program. FIG. 1 shows a typical microprocessor (20) that has a central processing unit (also referred to and known in the art as “CPU” or “execution unit”) (22), a memory controller (also known in the art as “load/store unit”) (24), and on-board, or level 1 (“L1”) cache memory (26). Cache memory is a region of fast memory that holds copies of data. Further, the microprocessor (20) is connected to both a main memory (28) of the computer system and an external, or level 2 (“L2”) cache memory (30).
One goal of a computer system is to efficiently and accurately execute, i.e., carry out, instructions provided by the computer system's users and computer programs. The execution of instructions is carried out by the CPU (22). Data requested by the CPU (22) to carry out an instruction are fetched by the memory controller (24) and loaded into internal registers (32) of the CPU (22). Upon command, the CPU (22) searches for the requested data in the internal registers (32). If the requested data is not available in the internal registers (32), the memory controller (24) first searches for the requested data in the on-board cache memory (26). If the requested data is not found in the on-board cache memory (26), the memory controller (24) next searches in the external cache memory (30). If this search turns out unsuccessful, the memory controller (24) retrieves the requested data from the slowest form of memory, the main memory (28).
In order for a CPU to execute instructions provided by a particular computer program, that particular computer program must have control of the CPU. Because the instructions of the computer program are carried out by the CPU, only one computer program at a time may be in control of the CPU. If an instruction belonging to a high-priority computer program requires use of the CPU, a CPU scheduler may take control of the CPU from a low-priority computer program currently using the CPU and give the control of the CPU to the high-priority program. Such a transfer of control of the CPU is typically done through the issuance of an “interrupt” notifying the CPU to stop its current process.
The transfer of control of the CPU is facilitated by an information transfer path commonly known in the art as a “bus.” A bus is used to connect components of a computer system. For example, a bus may used to connect the CPU to the main memory of the computer system. This bus may also be used to allow other computer resources, such as additional CPU's, access to the main memory. In other words, in such a multiple-CPU computer system, the CPUs share an access path to the main memory.
A request for access to the main memory, or other computer system resource, is called a “transaction.” A transaction is classified according to its type. For example, a transaction may be classified as a “read transaction” or “write transaction” depending on whether the transaction is a request to read data stored at a location in memory or to write data at a location in memory. As mentioned above, such transactions are facilitated by one or more buses. A computer system component connected to a bus is called an “agent.” A bus interface manages allocation of resources among one or more agents that may connected to a bus.
FIG. 2 shows a typical computer system (40) having a multi-agent bus (42). The multi-agent bus (42) is connected to a first agent (44), a second agent (46), and a last agent (48). Transactions on the multi-agent bus (42) are managed by a bus interface (50). The computer system (40) also has a main memory (52) having a desired memory location (54). If the first agent (44) requests access to the desired memory location (54), the bus interface (50) gives access to the main memory (52) along the multi-agent bus (42) to the first agent (44). However, if the first agent (44) and second agent (46) request access to the desired memory location (54) at the same time, the bus interface (50), depending on priority, allows only one of the requesting agents to transact information on the multi-agent bus (42) to or from the desired memory location (54). When the bus interface (50) is called upon to handle a situation in which there are multiple requests for access to the same memory location, the situation is called as “corner case situation.”
As apparent from the discussion above with reference to FIG. 2, the subject of a transaction along a bus is memory. Memory is used to store the data and instructions required to carry out various computer programs. A location in memory is called an “address.” For example, a particular instruction to be executed in a computer program may be stored at a location in the memory referred to as address 1000. In such a situation, there is a strong likelihood that the next instruction to be executed resides at the next following, i.e., adjacent, address, address 1001. It follows that subsequent instructions to be executed are likely to be found at addresses 1002, 1003 . . . Likewise, data is stored in memory in a similar manner.
A computer program typically has allocated to it one or more areas in memory for storage of instructions (also referred to as “instruction space”) and one or more areas in memory for storage of data (also referred to as “data space”). Moreover, input/output (“I/O”) devices, e.g., disk drives, monitors, keyboards, etc., also have allocated to them one or more areas in memory (also referred to as “I/O space”).
The predictability of addresses at which instructions and data reside in memory allows for improved efficiency in computer design and operation. As exemplified above, if the execution of a computer program involves a transaction that requires the access of address 1000 in memory, then there exists a strong likelihood that address locations adjacent to address 1000 are going to be accessed for the subsequent execution of the computer program. A memory cache exploits this likelihood by caching, i.e., temporarily storing, instructions and data at the adjacent locations so that the CPU has quicker access to the instructions and data. Thus, the memory cache helps enhance the efficiency of the execution of the computer program.
Although a memory cache helps improve program execution efficiency, other computer system components require improvement. In the case of a multi-agent bus, such as the one shown in FIG. 2, the design of a bus interface is challenging because the number of potential transactions on the multi-agent bus exponentially increases as the number of agents connected to multi-agent bus increases. The complexity of a multi-agent bus makes thorough testing and verification of bus design difficult due to the number of possible test cases.